package pers.qianyu.month_202011.date_20201124;

/**
 * 206. 反转链表
 * https://leetcode-cn.com/problems/reverse-linked-list/
 *
 * @author mizzle rain
 * @date 2020-11-24 22:53
 */
public class ReverseList {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        return recur(head);
    }

    /**
     * 递归法
     */
    private ListNode recur(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    /**
     * 迭代法
     */
    public ListNode reverseList2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p = head, newList = null;
        while (p != null) {
            ListNode temp = p.next;
            p.next = newList;
            newList = p;
            p = temp;
        }
        return newList;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
